1. Field of the Invention
The present invention relates to digital data processing systems and in particular, to a processing means and method for performing fast Fourier transforms using balanced coefficients.
2. Description of the Prior Art
The Fourier transform operation is well-known and a discrete Fourier transform algorithm by Berglund and a fast Fourier transform algorithm by Cooley and Tukey are discussed at length in a book entitled The Fast Fourier Transform and Its Applications by E. Brigham, 1988 by Prentice-Hall. The fast Fourier transform (FFT) is a widely used signal processing and analysis concept. Availability of special purpose hardware in both the commercial and military sectors has led to sophisticated signal processing systems based on the features of FFT. Additionally, implementation of FFT algorithms can be done on large mainframe computers or on the ubiquitous personal computers. The minimum apparatus for performing a fast Fourier transform comprises a processor, a random access memory, a program stored in read only memory, memory addressing means and a communal data bus.
The discrete Fourier transform, and its derivation, the fast Fourier transform (FFT), predict that a continuous waveform can be represented in the frequency domain and in the time domain by the sums of complex series of terms, both of which involve a set of Fourier coefficients. It is in the nature of the transform process that calculations of all frequency components, from zero frequency upwards, must be performed in every transformation. The computational power required to transform from the time domain to the frequency domain is enormous. The computational power needed requires a lot of memory and uses a lot of electrical energy with its accompanying heating effects. This makes FFT processors large, heavy and expensive.
All available literature indicates that for an FFT of size 2.sup.p a total of 2.sup.p coefficients are required. Providing the memory storage for this many coefficients increases the FFT product cost, size, weight and power.